câu 4 em hãy dùng thuật toán tìm kiếmm nhị phân để biểu diễn các bước thực hiện tìm số 13 trong dãy số...
Đọc tiếp
câu 4 em hãy dùng thuật toán tìm kiếmm nhị phân để biểu diễn các bước thực hiện tìm số 13 trong dãy số sau
| 7 | 8 | 4 | 9 | 2 | 13 | 5 | 20 |
K
Khách
Hãy nhập câu hỏi của bạn vào đây, nếu là tài khoản VIP, bạn sẽ được ưu tiên trả lời.
Những câu hỏi liên quan
QT
Quoc Tran Anh Le
Giáo viên
9 tháng 11 2023
Sau lần chia đôi đầu tiên, pham vi tìm kiếm còn lại n/2 số, sau khi chia đôi lần thứ hai, dãy còn lại n/4 số, sau khi chia đôi lần thứ dãy còn lại n/8, …sau khi chia đôi lần k dãy còn lại n/2.mũ k. Kết thúc khi 2 mũ k sấp xỉ n.
13 tháng 12 2023
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
ll a[]={10,2,5,12,20,6,8,15,18}; //mảng đã cho
ll n=sizeof(a)/sizeof(a[0]); //độ dài mảng
sort(a,a+n); //sắp xếp mảng
//Thuật toán tìm kiếm nhị phân
ll l=0, r=n-1;
while(l<=r) {
ll mid=(l+r)/2; //Tìm phần tử giữa left và right
if(a[mid]<15) l=mid+1; //Vì từ đoạn [0,mid] thì phần tử nhỏ hơn 15 nên ta duyệt từ khoảng (mid,r]
else r=mid-1; //vì thấy nên rút r để thu hẹp phạm vi
}
cout << l+1; //in ra kq (vì bắt đầu từ 0 đến n-1 nên phải tăng thêm để ra vị trí đúng)
}
(Bạn có thể dựa vào code mình để rút ra các bước)
Chúc bạn học tốt!
NQ
Nguyễn Quốc Đạt
Giáo viên
22 tháng 10 2023
a)
import time
def linear_search(arr, x):
"""
Tìm kiếm tuyến tính trong dãy arr để tìm giá trị x.
Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.
"""
n = len(arr)
for i in range(n):
if arr[i] == x:
return i
return -1
# Dãy số A
A = [3, 1, 0, 10, 13, 16, 9, 7, 5, 11]
# Phần tử cần tìm kiếm
C = 9
# Bắt đầu đo thời gian
start_time = time.perf_counter()
# Tìm kiếm phần tử C trong dãy A
result = linear_search(A, C)
# Kết thúc đo thời gian
end_time = time.perf_counter()
if result != -1:
print(f"Phần tử {C} được tìm thấy tại vị trí {result} trong dãy A.")
else:
print(f"Phần tử {C} không có trong dãy A.")
print(f"Thời gian thực hiện thuật toán: {end_time - start_time} giây.")
b)
import time
def binary_search(arr, x):
"""
Tìm kiếm nhị phân trong dãy arr để tìm giá trị x.
Trả về vị trí của x trong dãy nếu x được tìm thấy, -1 nếu không tìm thấy.
"""
left, right = 0, len(arr) - 1
while left <= right:
mid = (left + right) // 2
if arr[mid] == x:
return mid
elif arr[mid] < x:
left = mid + 1
else:
right = mid - 1
return -1
# Dãy số A đã được sắp xếp
A = [0, 1, 3, 5, 7, 9, 10, 11, 13, 16]
# Phần tử cần tìm kiếm
C = 9
# Bắt đầu đo thời gian
start_time = time.perf_counter()
# Tìm kiếm phần tử C trong dãy A bằng thuật toán tìm kiếm nhị phân
result = binary_search(A, C)
# Kết thúc đo thời gian
end_time = time.perf_counter()
if result != -1:
print(f"Phần tử {C} được tìm thấy tại vị trí {result} trong dãy A.")
else:
print(f"Phần tử {C} không có trong dãy A.")
print(f"Thời gian thực hiện thuật toán: {end_time - start_time} giây.")
-Thời gian thực hiện ở câu a là 8.99999,thời gian thực hiện ở câu b là 6,49999 giây.
9 tháng 4 2021
Nếu ở b2 khi S<=5 thì ta có tổng cộng 8 vòng lặp
Cách làm
B1: S:=13, x:=1
B2: Nếu S<=5 thì sang b4
B3: S:=S-x tức 13-1 và quay lại b2 cho đến khi 13 - 8 lần 1 thì kq sai, không vào vòng lặp nữa thì:
B4: S=5 và kết thúc thuật toán
Mình chỉ biết cách làm bài kiểu này thôi! Nếu đúng thì tham khảo bài mình nhé! Và lần sau bạn cần viết đúng các dấu hiệu để không làm sai đề bài nha :D
Dãy số sau khi sắp xếp tăng dần: 2; 4; 5; 7; 8; 9; 13; 20
Vòng lặp thứ nhất: Chia đôi dãy số, ta thấy 13 > 7 nên ta bỏ phần bên trái. Dãy số còn lại: 8; 9; 13; 20
Vòng lặp thứ hai: Chia đôi dãy số, ta thấy 13 > 9 nên ta bỏ phần bên trái. Dãy số còn lại; 13; 20
Vòng lặp thứ ba: Chia đôi dãy số, ta thấy 13 = 13 nên dừng tìm kiếm.
Thông báo kết quả tìm kiếm: số 13 được tìm thấy sau lần lặp thứ ba